#include <iostream>
#include <vector>
#include <Vector.hpp>
#include <queue>

using namespace std;
class Solution
{
public:
    vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k)
    {
        using dataS = pair<int, pair<int, int>>;
        auto cmp = [](const dataS &a, const dataS &b)
        {
            return a.first > b.first;
        };

        priority_queue<dataS, vector<dataS>, decltype(cmp)> pq(cmp);
        /*
        如果同时对两端进行增加,会出现数据重复,所以提前将第一组加入,然后后续只调整第二个数据的索引
        */
        for(int i = 0; i < nums1.size() && i < k; i++){
            pq.push({nums1[i] + nums2[0], {i, 0}});
        }
        vector<vector<int>> res;
        while (res.size() < k)
        {
            int i1 = pq.top().second.first;
            int i2 = pq.top().second.second;
            res.push_back({nums1[i1], nums2[i2]});
            //res.push_back({i1, i2});
            pq.pop();
            if (i2 < nums2.size() - 1)
                pq.push({nums1[i1] + nums2[i2 + 1], {i1, i2 + 1}});
        }
        return res;
    }
};
int main()
{
    cout << "Code373" << endl;
    Solution s;
    vector<vector<int>> res = s.kSmallestPairs(vector<int>{1, 2, 4, 5, 6}, vector<int>{3, 5, 7, 9}, 20);
    Print2DVector(res);
    return 0;
}